import java.util.ArrayList;
import java.util.List;


public class FloydInGraph {

    /**
     * 图	邻接矩阵 		最短路径		弗洛伊德算法
     */
    public static int INF=Integer.MAX_VALUE;
    //dist[i][j]=INF<==>no edges between i and j
    public int[][] dist;
    //the distance between i and j.At first,dist[i][j] is the weight of edge [i,j]
    public int[][] path;
public List<Integer> result=new ArrayList<Integer>();

//    public static void main(String[] args) {
//        FloydInGraph graph=new FloydInGraph(10);
//        int[][] matrix={
//                {INF,960,500,INF,INF,INF,INF,INF,INF,INF},
//                {960,INF,1500,1000,INF,INF,INF,INF,INF,INF},
//                {500,1500,INF,1280,INF,INF,INF,INF,INF,INF},
//                { INF,1000,1280,INF,900,INF,INF,INF,INF,INF},
//                {INF,INF,INF,INF,INF,1010,INF,INF,INF,INF},
//                {INF,INF,INF,INF,1010,INF,	800,INF,INF,INF},
//                {INF,INF,INF,INF,INF,INF,INF	,1060,INF,INF},
//                {INF,INF,INF,INF,INF,INF,1060,INF,700,INF},
//                {INF,INF,INF,INF,INF,INF,INF,INF,INF,1250},
//                {INF,INF,INF,INF,INF,INF,INF,INF,1250,INF},
//        };
//        int begin=9;
//        int end=3;
//        graph.findCheapestPath(begin,end,matrix);
//        List<Integer> list=graph.result;
//        System.out.println(begin+" to "+end+",the cheapest path is:");
//        System.out.println(list.toString());
//        System.out.println(graph.dist[begin][end]);
//    }

    public  void findCheapestPath(int begin,int end,int[][] matrix){
        floyd(matrix);
        result.add(begin);
        findPath(begin,end);
        result.add(end);
    }

    public void findPath(int i,int j){
        int k=path[i][j];
        if(k==-1)return;
        findPath(i,k);
        result.add(k);
        findPath(k,j);
    }
    public  void floyd(int[][] matrix){
        int size=matrix.length;
        //initialize dist and path
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                path[i][j]=-1;
                dist[i][j]=matrix[i][j];
            }
        }
        for(int k=0;k<size;k++){
            for(int i=0;i<size;i++){
                for(int j=0;j<size;j++){
                    if(dist[i][k]!=INF&&
                            dist[k][j]!=INF&&
                            dist[i][k]+dist[k][j]<dist[i][j]){//dist[i][k]+dist[k][j]>dist[i][j]-->longestPath
                        dist[i][j]=dist[i][k]+dist[k][j];
                        path[i][j]=k;
                    }
                }
            }
        }

    }

    public FloydInGraph(int size){
        this.path=new int[size][size];
        this.dist=new int[size][size];
    }
}

